package com.atwy.graph.undirectedgraph;

/**
 * @Author: 小王子火
 * @Date: 2022/3/16
 * 求一幅图的连通分量
 * 连通分量：无向图的极大连通子图。任何连通图的连通分量只有一个，即是自身。
 * 连通性：在无向图中，顶点v到顶点w有路径，则称v和w是连通的
 * 连通图：无向图中，任意两个不同的顶点都连通（即由有路径），则称该图是连通图。
 *
 * 求连通分量的目的：为了确定从图中的一个顶点是否能待定另一个顶点。也就是图中任意两个顶点之间是否有路径可达
 */
public class ConnectedComponent {
    /**
     * 记录某个顶点是否被访问到
     */
    private boolean[] marked;

    /**
     * 记录某个顶点所在连通分量标识符（0-count()-1）
     */
    private int[] id;
    /**
     * 连通分量标识符，从0开始记录
     */
    private int count;

    public ConnectedComponent(IGraph graph) {
        marked = new boolean[graph.V()];
        id = new int[graph.V()];
        for (int s=0;s<graph.V();s++){
            if(!marked[s]){
                dfs(graph,s);
                // 访问图中所有顶点，dfs可以访问s所能到底的所有顶点
                // 如果存在某个顶点不和s在一个连通分量里，则count+1
                count++;
            }
        }
    }

    private void dfs(IGraph graph, int v) {
        // count++在dfs之后，所有一个递归链中的count是相同的
        // 这样就可以用count作为连通分量的标识符了
        id[v] = count;
        for (int w : graph.adj(v)){
            if(!marked[w]){
                dfs(graph,w);
            }
        }

    }

    /**
     * 判断顶点v和w是否在同一个连通分量中，即判断是否连通
     * @param v
     * @param w
     * @return
     */
    public boolean isConnected(int v ,int w){
        return id[v] == id[w];
    }

    public int[] id(){
        return id;
    }

    public int count(){
        return count;
    }
}
